The present invention is related to a computer graphics system. More specifically, the present invention is related to view volume clip-check by a computer graphics system.
Clipping and Clip-checking
In a computer graphics system, the final two dimensional images being displayed are generated from raw three dimensional data through a sequence of processing steps. These three dimensional data include locations and geometry information about graphics objects and a hypothetical viewer. Typically, these three dimensional data are first stored in object coordinates of an object space, wherein graphics objects are represented independent of the viewer. Then, graphics objects and the viewer are transformed into a different space (with different coordinates) in order to relate these graphics objects to the viewer. In so doing, these graphics objects will be displayed as if seen through the eyes of the viewer. Next, graphics objects are clipped to fit the viewing volume of the viewer because what the viewer will see is finite in scope. Finally, the remaining three dimensional data undergo further processing steps to become two dimensional images stored in a frame buffer right before these two dimensional images are displayed.
In particular, the process of clipping geometry of graphics objects to fit the viewing volume actually involves at least three steps: transformation of the object space, clip-checking and clipping. The first step involved is called model view projection (MVP). Typically, clip-checking is not done in the object space even though three dimensional data are initially represented in object coordinates within the object space. Various transformations collectively called MVP is performed on the object space to create what is called a clip space. In so doing, the mathematical operations of clip-checking are reduced to simplified forms, thus facilitating the efficiency of clip-checking.
The second step involved is called clip-checking. In the clip-checking step, geometry of graphics objects is compared with the viewing volume of the viewer. Or more specifically, geometry of graphics object is compared with the frustum of the viewing volume. The motivation here is that the viewer sees only what is inside of the frustum: anything outside of the frustum will not be needed to generate the final two dimensional images. Thus, anything outside of the frustum is excluded (culled away) from undergoing further unnecessary processing. Also during clip-checking, if a certain portion of the geometry of graphics objects protrudes outside of the frustum, that certain portion will be designated as xe2x80x9cto be clipped away.xe2x80x9d The designated protruding portion will then be clipped away during the third step: the clipping step. Accordingly, this clipping step is performed within the clip space.
Prior Art Implementations of Clip-checking and Clipping
In a computer graphics system, the processing steps are allocated between the CPU (central processing unit) and the graphics pipeline. Specifically, the graphics pipeline is implemented to perform processing steps that are particularly well suited in a forward flow manner. In so doing, the graphics pipeline offsets the CPU""s graphic processing load. As a result, the processing steps can be efficiently performed, thus improving the overall throughput of the computer graphics system.
In one prior art approach, clipping is incorporated as a part of a graphics pipeline. Unfortunately, clipping is xe2x80x9cexpensivexe2x80x9d to perform within the graphics pipeline because clipping involves algorithms with branching behaviors. These branching behaviors from clipping algorithms clash against forward flow characteristics of any pipeline architecture. Moreover, clipping requires continual fetching and updating three dimensional data such as vertices of graphics objects represented within the object space. As such, if clipping is designed as a part of the graphics pipeline, the bus coupling the CPU and the graphics pipeline will be burdened with fetching and updating three dimensional data between the CPU and the graphics pipeline. In fact, bus bandwidth could be severely decreased by data communication between the CPU and the graphics pipeline, thus making bus congestion likely.
In another prior art approach, clipping is moved from the graphics pipeline to the CPU. By relying on the CPU to perform clipping, this approach solves the above problem of using a graphics pipeline""s forward flow method to perform algorithms with branching behaviors. This approach also solves the above problem of congesting the bus. However, this prior art approach in turn introduces new problems of its own.
One new problem is over-burdening the CPU of the computer graphics system. Importantly, the CPU is not only over-burdened simply because it performs the extra processing of clipping that used to be performed by the graphics pipeline. The CPU is over-burdened at least for two additional reasons. First, in order to clip geometry of graphics objects to fit within the frustum, clip-checking is performed prior to clipping. But because clipping is performed by the CPU, and because clip-checking is performed prior to clipping, clip-checking is also performed by the CPU and not performed by the graphics pipeline. Second, in order to clip-check graphics objects, graphics objects in object coordinates are first transformed by a MVP matrix into graphics objects in clip coordinates within a clip space. Specifically, performing clip-checking within the clip space simplifies the mathematical operations of clip-checking geometry. As such, the CPU also performs MVP matrix multiplications in addition to clip-checking and clipping. Accordingly, in this prior art approach, the CPU not only is performing clipping, but also MVP matrix multiplication and clip-checking prior to clipping. Thus, the CPU is over-burdened. And, throughput of the computer graphics system is decreased.
Furthermore, another problem with this prior art approach is under-utilization (or waste) of the graphics pipeline""s processing capability and strength. Specifically, as mentioned above, MVP matrix multiplication is now also designed to be performed by the CPU instead of the graphics pipeline. However, matrix multiplication is particular well suited for forward flow processing modal of the graphics pipeline. As such, performing matrix multiplication by the CPU does not take advantage of the graphics pipeline""s efficiency in performing matrix multiplication. Thus, the graphics pipeline""s processing capability is under-utilized. And again, throughput of the computer graphics system is decreased.
Thus, a need exists for a computer graphics system to perform clipping without disrupting the graphics pipeline by branching behavior of the clipping algorithms. A need also exists for a computer graphics system to perform clipping without decreasing the bus bandwidth between the CPU and the graphics pipeline. A further need exists for a computer graphics system to perform clipping without over-burdening the CPU. Yet still a need exists for a computer graphics system to perform clipping without under-utilizing the processing capability of the graphics pipeline.
Fortunately, as will be explained in the following pages, the present invention successfully answers all of the needs stated above with a new approach to clip-checking.
The present invention is drawn to a method and a system for performing view volume clip-check. Until the present invention, view volume clip-check by a computer graphics system had been performed within the context of a clip space with its clip coordinates. However, the present invention performs view volume clip-check within an object space with its object coordinates. In so doing, the present invention overcomes the problems of the prior art approaches in clipping. In particular, the present invention performs clipping without disrupting forward flow of the graphic pipeline. Moreover, the present invention performs clipping without wasting bus bandwidth. Furthermore, the present invention performs clipping without over-burdening the CPU. Further yet still, the present invention performs clipping without under utilizing the graphic pipeline. In addition, the present invention retains the mathematical simplicity of clip-checking even in the context of the object space. Consequently, throughput of the computer graphics system is advantageously increased.
In one embodiment of the present invention, a frustum (within a view volume) in a clip space is back projected into an object space as a back projected frustum. Within the object space, a regularized volume approximates the back projected frustum such that the regularized volume occupies most of the back projected frustum. Then, geometry of graphics objects is clip-checked against this regularized volume within the object space. Clipping is performed if clip-checking indicates that clipping is required on this geometry of graphics objects. Model view projection (MVP) is performed following clip-checking if no clipping is indicated; MVP is performed following clipping if clipping is indicated.
All in all, the present embodiment departs from the prior art methodology of clip-checking. The new clip-checking methodology of the present embodiment in turn enables advantageous arrangement of graphics processing steps. Specifically, back projection, clip-checking and clipping are all performed by the CPU rather than by the graphics pipeline. Thus advantageously, branching behaviors of clipping do not disrupt forward flow characteristic of the graphics pipeline. Also, bus bandwidth is not wasted on passing clipping data between the graphics pipeline and the CPU.
On the other hand, MVP is performed by the graphics pipeline rather than by the CPU. Thus advantageously, the CPU is not burdened with performing a step (i.e., matrix multiplication of MVP) that is particularly well suited for the graphics pipeline""s forward flow processing approach. Also, the pipeline is used to its full capability by performing MVP.
Furthermore, in the present embodiment, using the regularized volume for clip-checking retains all of the benefits provided by the prior art approaches for clip-checking. Through the regularized volume within the object space, the mathematical simplicity of performing clip-checking within the clip space (prior art) is still retained in clip-checking within the object space.
These and other objects and advantages of the present invention will no doubt become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.